package com.leet.code.lcof;

import java.util.Arrays;
import java.util.LinkedList;

public class Code59_1 {
    public static void main(String[] args) {
        int[] nums = {-7, -8, 7, 5, 7, 1, 6, 0};
        System.out.println(Arrays.toString(new Code59_1().maxSlidingWindow(nums, 4)));
    }

    public int[] maxSlidingWindow(int[] nums, int k) {
        if (nums.length == 0 || k == 1) {
            return nums;
        }
        int[] result = new int[nums.length - k + 1];

        int i = 0;
        LinkedList<Integer> list = new LinkedList<>();

        for (; i < k; i++) {
            while (!list.isEmpty() && list.getLast() < nums[i]) {
                list.removeLast();
            }
            list.add(nums[i]);
        }
        result[0] = list.getFirst();

        for (; i < nums.length; i++) {
            if (list.getFirst() == nums[i - k]) {
                list.removeFirst();
            }
            while (!list.isEmpty() && list.getLast() < nums[i]) {
                list.removeLast();
            }
            list.add(nums[i]);
            result[i - k + 1] = list.getFirst();

        }
        return result;
    }

}
